class Solution {
public:
    bool check(int(&hash1)[150], int(&hash2)[150], string& t)
    {
        for (int i = 0; i < t.size(); i++)
        {
            if (hash1[t[i]] < hash2[t[i]])
            {
                return false;
            }
        }

        return true;
    }

    string minWindow(string s, string t)
    {
        int hash1[150] = { 0 };
        int hash2[150] = { 0 };

        for (int i = 0; i < t.size(); i++)
        {
            hash2[t[i]]++;
        }

        int pos = 0, len = INT_MAX;
        for (int rhs = 0, lhs = 0; rhs < s.size(); rhs++)
        {
            hash1[s[rhs]]++;

            //check
            while (check(hash1, hash2, t))
            {
                if (len > rhs - lhs + 1)
                {
                    len = rhs - lhs + 1;
                    pos = lhs;
                }
                hash1[s[lhs++]]--;
            }
        }

        len = len == INT_MAX ? 0 : len;
        return string(s.begin() + pos, s.begin() + pos + len);
    }
};

class Solution {
public:

    string minWindow(string s, string t)
    {
        int hash1[128] = { 0 };
        int hash2[128] = { 0 };

        int hash_size = 0;
        for (int i = 0; i < t.size(); i++)
        {
            if (hash2[t[i]]++ == 0) hash_size++;           
        }

        int pos = 0, len = INT_MAX;
        for (int rhs = 0, lhs = 0, count = 0; rhs < s.size(); rhs++)
        {
            hash1[s[rhs]]++;
            if (hash1[s[rhs]] == hash2[s[rhs]]) count++;

            //check       
            while (count == hash_size)
            {
                if (len > rhs - lhs + 1)
                {
                    len = rhs - lhs + 1;
                    pos = lhs;
                }

                if (hash1[s[lhs]] == hash2[s[lhs]]) count--;
                hash1[s[lhs++]]--;
            }
        }

        len = len == INT_MAX ? 0 : len;
        return string(s.begin() + pos, s.begin() + pos + len);
    }
};